/*
 * contrib/intarray/_int_gist.c
 */
#include "postgres.h"

#include <limits.h>

#include "_int.h"
#include "access/gist.h"
#include "access/reloptions.h"
#include "access/stratnum.h"

#define GETENTRY(vec,pos) ((ArrayType *) DatumGetPointer((vec)->vector[(pos)].key))

/*
 * 控制压缩键的最大稀疏度。
 *
 * 这一限制的上限安全界限是可分配最大数组大小的一半。较低的界限会提供更多保证，以防病态数据消耗过多的 CPU 和内存，但代价是可能会破坏（在某种程度上）可用的索引。
 */
#define MAXNUMELTS (Min((MaxAllocSize / sizeof(Datum)),((MaxAllocSize - ARR_OVERHEAD_NONULLS(1)) / sizeof(int)))/2)
/* 或者: #define MAXNUMELTS 1000000 */

/*
** GiST 支持方法
*/
PG_FUNCTION_INFO_V1(g_int_consistent);
PG_FUNCTION_INFO_V1(g_int_compress);
PG_FUNCTION_INFO_V1(g_int_decompress);
PG_FUNCTION_INFO_V1(g_int_penalty);
PG_FUNCTION_INFO_V1(g_int_picksplit);
PG_FUNCTION_INFO_V1(g_int_union);
PG_FUNCTION_INFO_V1(g_int_same);
PG_FUNCTION_INFO_V1(g_int_options);


/*
** _intments 的 GiST 一致性方法
** 如果所有数据项 x 在条目下，满足谓词 x op query == false，则应返回 false，其中 op 是 pg_amop 表中与策略对应的操作符。
*/
Datum g_int_consistent(PG_FUNCTION_ARGS)
{
	GISTENTRY  *fc_entry = (GISTENTRY *) PG_GETARG_POINTER(0);
	ArrayType  *fc_query = PG_GETARG_ARRAYTYPE_P_COPY(1);
	StrategyNumber fc_strategy = (StrategyNumber) PG_GETARG_UINT16(2);

	/* Oid		subtype = PG_GETARG_OID(3); */
	bool	   *fc_recheck = (bool *) PG_GETARG_POINTER(4);
	bool		fc_retval;

	/* 这在 RTSameStrategyNumber 之外是准确的 */
	*fc_recheck = (fc_strategy == RTSameStrategyNumber);

	if (fc_strategy == BooleanSearchStrategy)
	{
		fc_retval = execconsistent((QUERYTYPE *) fc_query,
								(ArrayType *) DatumGetPointer(fc_entry->key),
								GIST_LEAF(fc_entry));

		pfree(fc_query);
		PG_RETURN_BOOL(fc_retval);
	}

	/* 排序查询以加快搜索，关键字已排序 */
	CHECKARRVALID(fc_query);
	PREPAREARR(fc_query);

	switch (fc_strategy)
	{
		case RTOverlapStrategyNumber:
			fc_retval = inner_int_overlap((ArrayType *) DatumGetPointer(fc_entry->key),
									   fc_query);
			break;
		case RTSameStrategyNumber:
			if (GIST_LEAF(fc_entry))
				DirectFunctionCall3(g_int_same,
									fc_entry->key,
									PointerGetDatum(fc_query),
									PointerGetDatum(&fc_retval));
			else
				fc_retval = inner_int_contains((ArrayType *) DatumGetPointer(fc_entry->key),
											fc_query);
			break;
		case RTContainsStrategyNumber:
		case RTOldContainsStrategyNumber:
			fc_retval = inner_int_contains((ArrayType *) DatumGetPointer(fc_entry->key),
										fc_query);
			break;
		case RTContainedByStrategyNumber:
		case RTOldContainedByStrategyNumber:

			/*
			 * 由于从 intarray 1.4 开始，这段代码是无法到达的，因为 <@
			 * 操作符已从操作类中移除。我们暂时保留它以支持旧版本的 SQL 定义。
			 */
			if (GIST_LEAF(fc_entry))
				fc_retval = inner_int_contains(fc_query,
											(ArrayType *) DatumGetPointer(fc_entry->key));
			else
			{
				/*
				 * 不幸的是，由于空数组可能在索引中的任何地方，我们必须搜索整个树。
				 */
				fc_retval = true;
			}
			break;
		default:
			fc_retval = false;
	}
	pfree(fc_query);
	PG_RETURN_BOOL(fc_retval);
}

Datum g_int_union(PG_FUNCTION_ARGS)
{
	GistEntryVector *fc_entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
	int		   *fc_size = (int *) PG_GETARG_POINTER(1);
	int32		fc_i,
			   *fc_ptr;
	ArrayType  *fc_res;
	int			fc_totlen = 0;

	for (fc_i = 0; fc_i < fc_entryvec->n; fc_i++)
	{
		ArrayType  *fc_ent = GETENTRY(fc_entryvec, fc_i);

		CHECKARRVALID(fc_ent);
		fc_totlen += ARRNELEMS(fc_ent);
	}

	fc_res = new_intArrayType(fc_totlen);
	fc_ptr = ARRPTR(fc_res);

	for (fc_i = 0; fc_i < fc_entryvec->n; fc_i++)
	{
		ArrayType  *fc_ent = GETENTRY(fc_entryvec, fc_i);
		int			fc_nel;

		fc_nel = ARRNELEMS(fc_ent);
		memcpy(fc_ptr, ARRPTR(fc_ent), fc_nel * sizeof(int32));
		fc_ptr += fc_nel;
	}

	QSORT(fc_res, 1);
	fc_res = _int_unique(fc_res);
	*fc_size = VARSIZE(fc_res);
	PG_RETURN_POINTER(fc_res);
}

/*
** GiST 压缩和解压缩方法
*/
Datum g_int_compress(PG_FUNCTION_ARGS)
{
	GISTENTRY  *fc_entry = (GISTENTRY *) PG_GETARG_POINTER(0);
	GISTENTRY  *fc_retval;
	ArrayType  *fc_r;
	int			fc_num_ranges = G_INT_GET_NUMRANGES();
	int			fc_len,
				fc_lenr;
	int		   *fc_dr;
	int			fc_i,
				fc_j,
				fc_cand;
	int64		fc_min;

	if (fc_entry->leafkey)
	{
		fc_r = DatumGetArrayTypePCopy(fc_entry->key);
		CHECKARRVALID(fc_r);
		PREPAREARR(fc_r);

		if (ARRNELEMS(fc_r) >= 2 * fc_num_ranges)
			ereport(ERROR,
					(errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
					 errmsg("input array is too big (%d maximum allowed, %d current), use gist__intbig_ops opclass instead",
							2 * fc_num_ranges - 1, ARRNELEMS(fc_r))));

		fc_retval = palloc(sizeof(GISTENTRY));
		gistentryinit(*fc_retval, PointerGetDatum(fc_r),
					  fc_entry->rel, fc_entry->page, fc_entry->offset, false);

		PG_RETURN_POINTER(fc_retval);
	}

	/*
	 * 叶条目永远不会再压缩一次，只有当 entry->leafkey
	 * ==true 时，因此现在我们只处理内部键
	 */

	fc_r = DatumGetArrayTypeP(fc_entry->key);
	CHECKARRVALID(fc_r);
	if (ARRISEMPTY(fc_r))
	{
		if (fc_r != (ArrayType *) DatumGetPointer(fc_entry->key))
			pfree(fc_r);
		PG_RETURN_POINTER(fc_entry);
	}

	if ((fc_len = ARRNELEMS(fc_r)) >= 2 * fc_num_ranges)
	{							/* 压缩 */
		if (fc_r == (ArrayType *) DatumGetPointer(fc_entry->key))
			fc_r = DatumGetArrayTypePCopy(fc_entry->key);
		fc_r = resize_intArrayType(fc_r, 2 * (fc_len));

		fc_dr = ARRPTR(fc_r);

		/*
		 * 此时 "len" 是我们将构建的范围数量。
		 * "lenr" 是我们最终必须通过合并移除的范围数量，我们必须小心不要移除超过这个数量的范围。
		 */
		fc_lenr = fc_len - fc_num_ranges;

		/*
		 * 初步假设我们可以将连续的整数合并为一个范围，但我们
		 * 必须计算每个移除的值，并在 lenr 用尽时停止。
		 */
		for (fc_j = fc_i = fc_len - 1; fc_i > 0 && fc_lenr > 0; fc_i--, fc_j--)
		{
			int			fc_r_end = fc_dr[fc_i];
			int			fc_r_start = fc_r_end;

			while (fc_i > 0 && fc_lenr > 0 && fc_dr[fc_i - 1] == fc_r_start - 1)
				--fc_r_start, --fc_i, --fc_lenr;
			fc_dr[2 * fc_j] = fc_r_start;
			fc_dr[2 * fc_j + 1] = fc_r_end;
		}
		/* 只需复制其余部分（如果有的话），作为常规范围 */
		for (; fc_i >= 0; fc_i--, fc_j--)
			fc_dr[2 * fc_j] = fc_dr[2 * fc_j + 1] = fc_dr[fc_i];

		if (++fc_j)
		{
			/*
			 * 将所有内容下移以从正确的位置开始
			 */
			memmove((void *) &fc_dr[0], (void *) &fc_dr[2 * fc_j], 2 * (fc_len - fc_j) * sizeof(int32));
		}

		/*
		 * 使 "len" 为数组元素的数量，而不是范围
		 */
		fc_len = 2 * (fc_len - fc_j);
		fc_cand = 1;
		while (fc_len > fc_num_ranges * 2)
		{
			fc_min = PG_INT64_MAX;
			for (fc_i = 2; fc_i < fc_len; fc_i += 2)
				if (fc_min > ((int64) fc_dr[fc_i] - (int64) fc_dr[fc_i - 1]))
				{
					fc_min = ((int64) fc_dr[fc_i] - (int64) fc_dr[fc_i - 1]);
					fc_cand = fc_i;
				}
			memmove((void *) &fc_dr[fc_cand - 1], (void *) &fc_dr[fc_cand + 1], (fc_len - fc_cand - 1) * sizeof(int32));
			fc_len -= 2;
		}

		/*
		 * 检查结果的稀疏度
		 */
		fc_lenr = internal_size(fc_dr, fc_len);
		if (fc_lenr < 0 || fc_lenr > MAXNUMELTS)
			ereport(ERROR,
					(errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
					 errmsg("data is too sparse, recreate index using gist__intbig_ops opclass instead")));

		fc_r = resize_intArrayType(fc_r, fc_len);
		fc_retval = palloc(sizeof(GISTENTRY));
		gistentryinit(*fc_retval, PointerGetDatum(fc_r),
					  fc_entry->rel, fc_entry->page, fc_entry->offset, false);
		PG_RETURN_POINTER(fc_retval);
	}
	else
		PG_RETURN_POINTER(fc_entry);
}

Datum g_int_decompress(PG_FUNCTION_ARGS)
{
	GISTENTRY  *fc_entry = (GISTENTRY *) PG_GETARG_POINTER(0);
	GISTENTRY  *fc_retval;
	ArrayType  *fc_r;
	int			fc_num_ranges = G_INT_GET_NUMRANGES();
	int		   *fc_dr,
				fc_lenr;
	ArrayType  *fc_in;
	int			fc_lenin;
	int		   *fc_din;
	int			fc_i;

	fc_in = DatumGetArrayTypeP(fc_entry->key);

	CHECKARRVALID(fc_in);
	if (ARRISEMPTY(fc_in))
	{
		if (fc_in != (ArrayType *) DatumGetPointer(fc_entry->key))
		{
			fc_retval = palloc(sizeof(GISTENTRY));
			gistentryinit(*fc_retval, PointerGetDatum(fc_in),
						  fc_entry->rel, fc_entry->page, fc_entry->offset, false);
			PG_RETURN_POINTER(fc_retval);
		}

		PG_RETURN_POINTER(fc_entry);
	}

	fc_lenin = ARRNELEMS(fc_in);

	if (fc_lenin < 2 * fc_num_ranges)
	{							/* 未压缩值 */
		if (fc_in != (ArrayType *) DatumGetPointer(fc_entry->key))
		{
			fc_retval = palloc(sizeof(GISTENTRY));
			gistentryinit(*fc_retval, PointerGetDatum(fc_in),
						  fc_entry->rel, fc_entry->page, fc_entry->offset, false);

			PG_RETURN_POINTER(fc_retval);
		}
		PG_RETURN_POINTER(fc_entry);
	}

	fc_din = ARRPTR(fc_in);
	fc_lenr = internal_size(fc_din, fc_lenin);
	if (fc_lenr < 0 || fc_lenr > MAXNUMELTS)
		ereport(ERROR,
				(errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
				 errmsg("compressed array is too big, recreate index using gist__intbig_ops opclass instead")));

	fc_r = new_intArrayType(fc_lenr);
	fc_dr = ARRPTR(fc_r);

	for (fc_i = 0; fc_i < fc_lenin; fc_i += 2)
	{
		/* 使用 int64 作为 j，以防 din[i + 1] 是 INT_MAX */
		for (int64 fc_j = fc_din[fc_i]; fc_j <= fc_din[fc_i + 1]; fc_j++)
			if ((!fc_i) || *(fc_dr - 1) != fc_j)
				*fc_dr++ = (int) fc_j;
	}

	if (fc_in != (ArrayType *) DatumGetPointer(fc_entry->key))
		pfree(fc_in);
	fc_retval = palloc(sizeof(GISTENTRY));
	gistentryinit(*fc_retval, PointerGetDatum(fc_r),
				  fc_entry->rel, fc_entry->page, fc_entry->offset, false);

	PG_RETURN_POINTER(fc_retval);
}

/*
** _intments 的 GiST 惩罚方法
*/
Datum g_int_penalty(PG_FUNCTION_ARGS)
{
	GISTENTRY  *fc_origentry = (GISTENTRY *) PG_GETARG_POINTER(0);
	GISTENTRY  *fc_newentry = (GISTENTRY *) PG_GETARG_POINTER(1);
	float	   *fc_result = (float *) PG_GETARG_POINTER(2);
	ArrayType  *fc_ud;
	float		fc_tmp1,
				fc_tmp2;

	fc_ud = inner_int_union((ArrayType *) DatumGetPointer(fc_origentry->key),
						 (ArrayType *) DatumGetPointer(fc_newentry->key));
	rt__int_size(fc_ud, &fc_tmp1);
	rt__int_size((ArrayType *) DatumGetPointer(fc_origentry->key), &fc_tmp2);
	*fc_result = fc_tmp1 - fc_tmp2;
	pfree(fc_ud);

	PG_RETURN_POINTER(fc_result);
}



Datum g_int_same(PG_FUNCTION_ARGS)
{
	ArrayType  *fc_a = PG_GETARG_ARRAYTYPE_P(0);
	ArrayType  *fc_b = PG_GETARG_ARRAYTYPE_P(1);
	bool	   *fc_result = (bool *) PG_GETARG_POINTER(2);
	int32		fc_n = ARRNELEMS(fc_a);
	int32	   *fc_da,
			   *fc_db;

	CHECKARRVALID(fc_a);
	CHECKARRVALID(fc_b);

	if (fc_n != ARRNELEMS(fc_b))
	{
		*fc_result = false;
		PG_RETURN_POINTER(fc_result);
	}
	*fc_result = true;
	fc_da = ARRPTR(fc_a);
	fc_db = ARRPTR(fc_b);
	while (fc_n--)
	{
		if (*fc_da++ != *fc_db++)
		{
			*fc_result = false;
			break;
		}
	}

	PG_RETURN_POINTER(fc_result);
}

/*****************************************************************
** 通用 GiST 方法
*****************************************************************/

typedef struct
{
	OffsetNumber pos;
	float		cost;
} SPLITCOST;

static int fc_comparecost(const void *fc_a, const void *fc_b)
{
	if (((const SPLITCOST *) fc_a)->cost == ((const SPLITCOST *) fc_b)->cost)
		return 0;
	else
		return (((const SPLITCOST *) fc_a)->cost > ((const SPLITCOST *) fc_b)->cost) ? 1 : -1;
}

/*
** _intments 的 GiST PickSplit 方法
** 我们使用 Guttman 的多项式时间分裂算法
*/
Datum g_int_picksplit(PG_FUNCTION_ARGS)
{
	GistEntryVector *fc_entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
	GIST_SPLITVEC *fc_v = (GIST_SPLITVEC *) PG_GETARG_POINTER(1);
	OffsetNumber fc_i,
				fc_j;
	ArrayType  *fc_datum_alpha,
			   *fc_datum_beta;
	ArrayType  *fc_datum_l,
			   *fc_datum_r;
	ArrayType  *fc_union_d,
			   *fc_union_dl,
			   *fc_union_dr;
	ArrayType  *fc_inter_d;
	bool		fc_firsttime;
	float		fc_size_alpha,
				fc_size_beta,
				fc_size_union,
				fc_size_inter;
	float		fc_size_waste,
				fc_waste;
	float		fc_size_l,
				fc_size_r;
	int			fc_nbytes;
	OffsetNumber fc_seed_1 = 0,
				fc_seed_2 = 0;
	OffsetNumber *fc_left,
			   *fc_right;
	OffsetNumber fc_maxoff;
	SPLITCOST  *fc_costvector;

#ifdef GIST_DEBUG
	elog(DEBUG3, "--------picksplit %d", fc_entryvec->n);
#endif

	fc_maxoff = fc_entryvec->n - 2;
	fc_nbytes = (fc_maxoff + 2) * sizeof(OffsetNumber);
	fc_v->spl_left = (OffsetNumber *) palloc(fc_nbytes);
	fc_v->spl_right = (OffsetNumber *) palloc(fc_nbytes);

	fc_firsttime = true;
	fc_waste = 0.0;
	for (fc_i = FirstOffsetNumber; fc_i < fc_maxoff; fc_i = OffsetNumberNext(fc_i))
	{
		fc_datum_alpha = GETENTRY(fc_entryvec, fc_i);
		for (fc_j = OffsetNumberNext(fc_i); fc_j <= fc_maxoff; fc_j = OffsetNumberNext(fc_j))
		{
			fc_datum_beta = GETENTRY(fc_entryvec, fc_j);

			/* 通过合并这些来计算浪费的空间 */
			/* size_waste = size_union - size_inter; */
			fc_union_d = inner_int_union(fc_datum_alpha, fc_datum_beta);
			rt__int_size(fc_union_d, &fc_size_union);
			fc_inter_d = inner_int_inter(fc_datum_alpha, fc_datum_beta);
			rt__int_size(fc_inter_d, &fc_size_inter);
			fc_size_waste = fc_size_union - fc_size_inter;

			pfree(fc_union_d);
			pfree(fc_inter_d);

			/*
			 * 这些是比我们已经看到的更有前途的分裂吗？
			 */

			if (fc_size_waste > fc_waste || fc_firsttime)
			{
				fc_waste = fc_size_waste;
				fc_seed_1 = fc_i;
				fc_seed_2 = fc_j;
				fc_firsttime = false;
			}
		}
	}

	fc_left = fc_v->spl_left;
	fc_v->spl_nleft = 0;
	fc_right = fc_v->spl_right;
	fc_v->spl_nright = 0;
	if (fc_seed_1 == 0 || fc_seed_2 == 0)
	{
		fc_seed_1 = 1;
		fc_seed_2 = 2;
	}

	fc_datum_alpha = GETENTRY(fc_entryvec, fc_seed_1);
	fc_datum_l = copy_intArrayType(fc_datum_alpha);
	rt__int_size(fc_datum_l, &fc_size_l);
	fc_datum_beta = GETENTRY(fc_entryvec, fc_seed_2);
	fc_datum_r = copy_intArrayType(fc_datum_beta);
	rt__int_size(fc_datum_r, &fc_size_r);

	fc_maxoff = OffsetNumberNext(fc_maxoff);

	/*
	 * 排序条目
	 */
	fc_costvector = (SPLITCOST *) palloc(sizeof(SPLITCOST) * fc_maxoff);
	for (fc_i = FirstOffsetNumber; fc_i <= fc_maxoff; fc_i = OffsetNumberNext(fc_i))
	{
		fc_costvector[fc_i - 1].pos = fc_i;
		fc_datum_alpha = GETENTRY(fc_entryvec, fc_i);
		fc_union_d = inner_int_union(fc_datum_l, fc_datum_alpha);
		rt__int_size(fc_union_d, &fc_size_alpha);
		pfree(fc_union_d);
		fc_union_d = inner_int_union(fc_datum_r, fc_datum_alpha);
		rt__int_size(fc_union_d, &fc_size_beta);
		pfree(fc_union_d);
		fc_costvector[fc_i - 1].cost = Abs((fc_size_alpha - fc_size_l) - (fc_size_beta - fc_size_r));
	}
	qsort((void *) fc_costvector, fc_maxoff, sizeof(SPLITCOST), fc_comparecost);

	/*
	 * 现在将区域在两个种子之间分开。该分割算法的一个重要特性是，分割向量 v 在其左向量和右向量中按顺序包含要分割的项的索引。我们在实际分割页面的代码中利用了这个特性进行合并。
	 *
	 * 为了提高效率，我们还将在此循环中放置新的索引元组。这在最后处理，当我们放置了所有现有元组且 i == maxoff + 1 时。
	 */


	for (fc_j = 0; fc_j < fc_maxoff; fc_j++)
	{
		fc_i = fc_costvector[fc_j].pos;

		/*
		 * 如果我们已经决定将此项放置在哪里，则直接放到右侧列表。否则，我们需要弄清楚哪个页面需要最少的扩展以存储该项。
		 */

		if (fc_i == fc_seed_1)
		{
			*fc_left++ = fc_i;
			fc_v->spl_nleft++;
			continue;
		}
		else if (fc_i == fc_seed_2)
		{
			*fc_right++ = fc_i;
			fc_v->spl_nright++;
			continue;
		}

		/* 好吧，哪个页面需要最少的扩展？ */
		fc_datum_alpha = GETENTRY(fc_entryvec, fc_i);
		fc_union_dl = inner_int_union(fc_datum_l, fc_datum_alpha);
		fc_union_dr = inner_int_union(fc_datum_r, fc_datum_alpha);
		rt__int_size(fc_union_dl, &fc_size_alpha);
		rt__int_size(fc_union_dr, &fc_size_beta);

		/* 选择将其添加到哪个页面 */
		if (fc_size_alpha - fc_size_l < fc_size_beta - fc_size_r + WISH_F(fc_v->spl_nleft, fc_v->spl_nright, 0.01))
		{
			pfree(fc_datum_l);
			pfree(fc_union_dr);
			fc_datum_l = fc_union_dl;
			fc_size_l = fc_size_alpha;
			*fc_left++ = fc_i;
			fc_v->spl_nleft++;
		}
		else
		{
			pfree(fc_datum_r);
			pfree(fc_union_dl);
			fc_datum_r = fc_union_dr;
			fc_size_r = fc_size_beta;
			*fc_right++ = fc_i;
			fc_v->spl_nright++;
		}
	}
	pfree(fc_costvector);
	*fc_right = *fc_left = FirstOffsetNumber;

	fc_v->spl_ldatum = PointerGetDatum(fc_datum_l);
	fc_v->spl_rdatum = PointerGetDatum(fc_datum_r);

	PG_RETURN_POINTER(fc_v);
}

Datum g_int_options(PG_FUNCTION_ARGS)
{
	local_relopts *fc_relopts = (local_relopts *) PG_GETARG_POINTER(0);

	init_local_reloptions(fc_relopts, sizeof(GISTIntArrayOptions));
	add_local_int_reloption(fc_relopts, "numranges",
							"number of ranges for compression",
							G_INT_NUMRANGES_DEFAULT, 1, G_INT_NUMRANGES_MAX,
							offsetof(GISTIntArrayOptions, num_ranges));

	PG_RETURN_VOID();
}
